!*******************************************************************************
!> author: Jacob Williams
!
!  Utility routines.

module csv_utils_m

    use, intrinsic :: iso_fortran_env, only: dp => real64, sp => real32, ip => int32
    use csv_config_m
    implicit none
    private

    integer, parameter :: max_size_for_insertion_sort = 20 !! max size for using insertion sort.

    character(len=*), parameter :: upper = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ' !! uppercase characters
    character(len=*), parameter :: lower = 'abcdefghijklmnopqrstuvwxyz' !! lowercase characters

    public :: unique
    public :: expand_vector
    public :: sort_ascending
    public :: lowercase_string

contains
!*******************************************************************************

!*******************************************************************************
!>
!  Add elements to the integer vector in chunks.

    pure subroutine expand_vector(vec, n, chunk_size, val, finished)


        integer, dimension(:), allocatable, intent(inout) :: vec
        integer, intent(inout) :: n           !! counter for last element added to `vec`.
                                               !! must be initialized to `size(vec)`
                                               !! (or 0 if not allocated) before first call
        integer, intent(in) :: chunk_size  !! allocate `vec` in blocks of this size (>0)
        integer, intent(in), optional :: val         !! the value to add to `vec`
        logical, intent(in), optional :: finished    !! set to true to return `vec`
                                               !! as its correct size (`n`)

        integer, dimension(:), allocatable :: tmp  !! temporary array

        if (present(val)) then
            if (allocated(vec)) then
                if (n == size(vec)) then
                    ! have to add another chunk:
                    allocate (tmp(size(vec) + chunk_size))
                    tmp(1:size(vec)) = vec
                    call move_alloc(tmp, vec)
                end if
                n = n + 1
            else
                ! the first element:
                allocate (vec(chunk_size))
                n = 1
            end if
            vec(n) = val
        end if

        if (present(finished)) then
            if (finished) then
                ! set vec to actual size (n):
                if (allocated(tmp)) deallocate (tmp)
                allocate (tmp(n))
                tmp = vec(1:n)
                call move_alloc(tmp, vec)
            end if
        end if

    end subroutine expand_vector
!*******************************************************************************

!*******************************************************************************
!>
!  Returns only the unique elements of the vector.

    function unique(vec, chunk_size) result(ivec_unique)


        integer, dimension(:), intent(in) :: vec        !! a vector of integers
        integer, intent(in) :: chunk_size  !! chunk size for adding to arrays
        integer, dimension(:), allocatable :: ivec_unique !! unique elements of `ivec`

        integer, dimension(size(vec)) :: ivec !! temp copy of vec
        integer :: i !! counter
        integer :: n !! number of unique elements

        ! first we sort it:
        ivec = vec ! make a copy
        call sort_ascending(ivec)

        ! add the first element:
        n = 1
        ivec_unique = [ivec(1)]

        ! walk through array and get the unique ones:
        if (size(ivec) > 1) then
            do i = 2, size(ivec)
                if (ivec(i) /= ivec(i - 1)) then
                    call expand_vector(ivec_unique, n, chunk_size, val=ivec(i))
                end if
            end do
            call expand_vector(ivec_unique, n, chunk_size, finished=.true.)
        end if

    end function unique
!*******************************************************************************

!*******************************************************************************
!>
!  Sorts an integer array `ivec` in increasing order.
!  Uses a basic recursive quicksort
!  (with insertion sort for partitions with \(\le\) 20 elements).

    subroutine sort_ascending(ivec)


        integer, dimension(:), intent(inout) :: ivec

        call quicksort(1, size(ivec))

    contains

        recursive subroutine quicksort(ilow, ihigh)

        !! Sort the array


            integer, intent(in) :: ilow
            integer, intent(in) :: ihigh

            integer :: ipivot !! pivot element
            integer :: i      !! counter
            integer :: j      !! counter

            if (ihigh - ilow <= max_size_for_insertion_sort .and. ihigh > ilow) then

                ! do insertion sort:
                do i = ilow + 1, ihigh
                    do j = i, ilow + 1, -1
                        if (ivec(j) < ivec(j - 1)) then
                            call swap(ivec(j), ivec(j - 1))
                        else
                            exit
                        end if
                    end do
                end do

            else if (ihigh - ilow > max_size_for_insertion_sort) then

                ! do the normal quicksort:
                call partition(ilow, ihigh, ipivot)
                call quicksort(ilow, ipivot - 1)
                call quicksort(ipivot + 1, ihigh)

            end if

        end subroutine quicksort

        subroutine partition(ilow, ihigh, ipivot)

        !! Partition the array, based on the
        !! lexical ivecing comparison.


            integer, intent(in) :: ilow
            integer, intent(in) :: ihigh
            integer, intent(out) :: ipivot

            integer :: i, ip

            call swap(ivec(ilow), ivec((ilow + ihigh)/2))
            ip = ilow
            do i = ilow + 1, ihigh
                if (ivec(i) < ivec(ilow)) then
                    ip = ip + 1
                    call swap(ivec(ip), ivec(i))
                end if
            end do
            call swap(ivec(ilow), ivec(ip))
            ipivot = ip

        end subroutine partition

    end subroutine sort_ascending
!*******************************************************************************

!*******************************************************************************
!>
!  Swap two integer values.

    pure elemental subroutine swap(i1, i2)


        integer, intent(inout) :: i1
        integer, intent(inout) :: i2

        integer :: tmp

        tmp = i1
        i1 = i2
        i2 = tmp

    end subroutine swap
!*******************************************************************************

!*******************************************************************************
!>
!  Returns lowercase version of the string.

    pure function lowercase_string(str) result(s_lower)


        character(len=*), intent(in) :: str      !! input string
        character(len=(len(str))) :: s_lower  !! lowercase version of the string

        integer :: i  !! counter
        integer :: j  !! index of uppercase character

        s_lower = str

        do i = 1, len_trim(str)
            j = index(upper, s_lower(i:i))
            if (j > 0) s_lower(i:i) = lower(j:j)
        end do

    end function lowercase_string
!*******************************************************************************

!*******************************************************************************
end module csv_utils_m
!*******************************************************************************
